#include <stdio.h>
#include <stdlib.h>
#define MAX 100
void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}
void quick_sort(int a[], int n)
{
    int stack[MAX];
    int top = -1;
    // 先入栈left
    stack[++top] = 0;
    // 在入栈right
    stack[++top] = n - 1;
    // 出栈时先出栈right 再出栈left
    while (top >= 0)
    {
        int right, left;
        right = stack[top--];
        left = stack[top--];
        int n = a[left];
        int i, j;
        i = left + 1, j = right;
        while (1)
        {
            while (a[i] < n)
            {
                i++;
            }
            while (a[j] > n)
            {
                j--;
            }
            if (i < j)
                swap(a[i], a[j]);
            else
                break;
        }
        swap(a[j], a[left]);
        if (left < j - 1)
        {
            stack[++top] = left;
            stack[++top] = j - 1;
        }
        if (j + 1 < right)
        {
            stack[++top] = j + 1;
            stack[++top] = right;
        }
    }
}

int main()
{
    /*******************code*******************/
    int a[] = {4, 3, 10, 8, 14, 13, 7, 30, 26, 17};
    quick_sort(a, 10);
    printf("quick_sort\n");
    for (int i = 0; i < 10; i++)
        printf("%3d", a[i]);
    printf("\n");
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
